﻿#define _SORT
//#define HIT_LOGGING

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.ComponentModel;
using System.Linq;
using System.Text;
using System.Reactive.Concurrency;
using System.Threading;
using System.Threading.Tasks;
using System.Runtime.InteropServices;
using System.Xaml;

using alib.BitArray;
using alib.Collections.ReadOnly;
using alib.Debugging;
using alib.Enumerable;
using alib.String.Builder;

using agree.configuration;

namespace agree
{
	public unsafe sealed class GlbCache : has_grammar_base, ISupportInitializeNotification
	{
		public GlbCache(IRtParent parent)
			: base(parent)
		{
		}

		GlbCacheEntry[][] glb_cache;
		int c_precached;
		TypesConfig.GlbCacheOptionsEnum glb_cache_opts;

		public new FeatMgr FeatMgr
		{
			get { return base.ftm; }
			set { base.FeatMgr = value; }
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void EndInit()
		{
			if (g == null)
				throw new Exception();
			if (bcpo == null)
				throw new Exception();
			if (ftm == null)
				throw new Exception();

			var opts = AgreeConfig.Types.GlbCacheOptions;
			if ((opts & (TypesConfig.GlbCacheOptionsEnum.PreCacheAuthoredTypes |
						TypesConfig.GlbCacheOptionsEnum.PreCacheBcpoTypes)) == 0)
				return;

			this.glb_cache_opts = AgreeConfig.Types.GlbCacheOptions;
			this.glb_cache = new GlbCacheEntry[AgreeConfig.Types.GlbCacheBucketCount][];

			/// Because the EtmNonBareType flag is deployed into the glb_cache as part of the type id, we
			/// defer pre-caching of GLBs until now, after features have been loaded.
			var tc = TaskControl.Scheduler;
			if (tc is CurrentThreadScheduler ||
				(opts & TypesConfig.GlbCacheOptionsEnum.PreCacheSpawnTask) == 0)
				PreCacheGlbs();
			else
				tc.Schedule<GlbCache>(this, (sch, _this) =>
				{
					ThreadPriority tp = Thread.CurrentThread.Priority;
					if ((opts & TypesConfig.GlbCacheOptionsEnum.PreCacheTaskLowerPriority) != 0)
						Thread.CurrentThread.Priority = ThreadPriority.BelowNormal;
					PreCacheGlbs();
					Thread.CurrentThread.Priority = tp;
					return EmptyDisposable.Instance;
				});

			g.glbc = this;
		}


		[DebuggerDisplay("{ToString(),nq}")]
		struct GlbCacheEntry
		{
			public GlbCacheEntry(uint k, Edge.Flag f)
			{
#if DEBUG && false
				if ((k & 0xC0000000) != 0)
					throw new Exception();
				var g = Grammar._singleton;
				if (g != null && g.tm != null && f != Edge.Flag.Bottom)
					if (((f & Edge.Flag.EtmNonBareType) != 0) != g.tm.type_arr[(int)(f & Edge.Flag.MultiIdMask)].HasAppropriateFeatures)
						throw new Exception();
#endif
				this.k = k;
				this.f = f;
#if HIT_LOGGING
				this.c_hits = 0;
#endif
			}
			public readonly uint k;
			public readonly Edge.Flag f;
#if HIT_LOGGING
			public int c_hits;
#endif
#if DEBUG && false
			public override string ToString()
			{
				TypeMgr tm = Grammars.DebugTypeMgr;
				if (tm == null)
					return "n/a";
				Type t0 = tm.type_arr[(ushort)k];
				Type t1 = tm.type_arr[k >> 16];
				return String.Format("{0} {1} => {2}", t0.Name, t1.Name, tm.TypeNameOrStringValue(f));
			}
			public override bool Equals(object obj)
			{
				if (!(obj is GlbCacheEntry))
					return false;
				GlbCacheEntry gce = (GlbCacheEntry)obj;
				return gce.k == k && gce.f == f;
			}
			public override int GetHashCode()
			{
				return (int)k ^ (int)f;
			}
#endif
		};


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public void PreCacheGlbs()
		{
			for (int id_lower = 1; id_lower < bcpo.type_arr.Length; id_lower++)
			{
				Type t_lower = bcpo.type_arr[id_lower];
				if (_precache_filter(t_lower))
				{
					Edge.Flag f_lower = t_lower.EdgeFlag;
					foreach (Type t_upper in t_lower.AllAncestors.Where(_precache_filter))
					{
						Debug.Assert(id_lower > t_upper._id);
						insert_cache_entry(k_compute(id_lower, t_upper._id), f_lower);
						c_precached++;
					}
				}
			}
		}
		bool _precache_filter(Type t)
		{
			if (t.c_children == 0 || t.IsTop)
				return false;
			if (t.IsGlb)
				return (glb_cache_opts & TypesConfig.GlbCacheOptionsEnum.PreCacheBcpoTypes) != 0;
			else
				return (glb_cache_opts & TypesConfig.GlbCacheOptionsEnum.PreCacheAuthoredTypes) != 0;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		void insert_cache_entry(uint k, Edge.Flag f)
		{
#if DEBUG && true
			uint id0 = (uint)(ushort)k;
			uint id1 = (uint)(k >> 16);
			Debug.Assert(id0 != 0 && id0 < id1);
			if (f != Edge.Flag.Bottom)
			{
				Debug.Assert(!f.IsStringFamilyValue());
				//((LatticeEdgeOperations)this).ValidateTypeFlag(f);
			}

			//Console.WriteLine("{0,20} {1,20} {2,20}",
			//    type_arr[id0].Name,
			//    type_arr[id1].Name,
			//    ((LatticeEdgeOperations)this).TypeNameOrStringValue(f));
#endif
			uint ix;
			GlbCacheEntry[] rge = glb_cache[ix = k % (uint)glb_cache.Length];
			if (rge == null)
				glb_cache[ix] = new[] { new GlbCacheEntry(k, f) };
			else
			{
#if _SORT
				glb_cache[ix] = copy_insert(k, f, rge);
#else
				GlbCacheEntry[] rgenew = new GlbCacheEntry[rge.Length + 1];
				rge.CopyTo(rgenew, 0);
				rgenew[rge.Length] = new GlbCacheEntry(k, f);
					// atomic publishing; don't care about lost entries due to race
				__refvalue(tr, GlbCacheEntry[]) = rgenew;
#endif
			}
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		GlbCacheEntry[] copy_insert(uint k, Edge.Flag f, GlbCacheEntry[] rge)
		{
			int c = rge.Length;
			Debug.Assert(c > 0);
			GlbCacheEntry[] rgenew = new GlbCacheEntry[c + 1];
			fixed (GlbCacheEntry* _src = rge, _dst = rgenew)
			{
				GlbCacheEntry* src = _src;
				int i = 0;
				do
				{
					if (k < src->k)
						break;
					_dst[i++] = *src++;
				}
				while (i < c);
				_dst[i++] = new GlbCacheEntry(k, f);
				while (i <= c)
					_dst[i++] = *src++;
			}
			return rgenew;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// 
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		static uint k_compute(int id0, int id1)
		{
			uint k;
			if (id0 < id1)
			{
				k = (uint)id0;
				*(short*)((long)&k + 2) = (short)id1;
			}
			else
			{
				k = (uint)id1;
				*(short*)((long)&k + 2) = (short)id0;
			}
			return k;
		}

		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		/// todo: more cache entries can be implied when *bottom* is found, see "bag of useful techniques" paper
		/// note: already measured using a direct code_arr and it was slower; presumably it's more important to
		/// keep the type_arr cache warm.
		/// todo: make sure callers are not trying to cache string *values*
		/// you *can* cache string subsumers, but use (Edge.Flag)StringType.m_id, not EtmString
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public Edge.Flag get_glb(Edge.Flag f0, Edge.Flag f1)
		{
#if DEBUG
			Debug.Assert(!(f0 | f1).IsStringFamilyType());
			tu.ValidateTypeFlag(f0);
			tu.ValidateTypeFlag(f1);
			Debug.Assert(f0 != f1 && f0 > 0 && f1 > 0);
			Debug.Assert(((f0 | f1) & Edge.Flag.EtmLeafType) == 0);
#endif

			int id0, id1;
			uint k = k_compute(id0 = (int)(f0 & Edge.Flag.MultiIdMask), id1 = (int)(f1 & Edge.Flag.MultiIdMask));

			Debug.Assert(id0 < bcpo.type_arr.Length && id1 < bcpo.type_arr.Length);

			GlbCacheEntry[] rge;
			if ((rge = glb_cache[k % (uint)glb_cache.Length]) != null)
			{
				uint i = 0;
#if _SORT
				Debug.Assert(rge.IsSorted(z => z.k));
				uint gk;
				do
					if ((gk = rge[i].k) == k)
					{
#if HIT_LOGGING
						rge[i].c_hits++;
#endif
						return rge[i].f;
					}
				while (gk < k && ++i < rge.Length);
#else
				do
				{
					if (rge[i].k == k)
					{
#if HIT_LOGGING
						rge[i].c_hits++;
#endif
						return rge[i].f;
					}
				}
				while (++i < rge.Length);
#endif
			}

			Edge.Flag f;
			BitArr ba;
			if ((ba = bcpo.type_arr[id0].bit_vec.AndWithHash(bcpo.type_arr[id1].bit_vec)) == null)
				f = Edge.Flag.Bottom;
			else
			{
				Type t_glb;
				bool b = bcpo.code_dict.TryGetValue(ba, out t_glb);
				Debug.Assert(b && !ba.IsAllZeros && !ba.IsAllOnes);
				f = t_glb.EdgeFlag;
			}
			insert_cache_entry(k, f);
			return f;
		}


		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		/// <summary>
		///
		/// </summary>
		///////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
		public String GlbCacheInfo()
		{
			int c_buckets = glb_cache.Length;
			int c_total = 0;
			int min = int.MaxValue;
			int max = int.MinValue;
			int c_lists = 0;
			int c_bot = 0;
			int c_sub = 0;
			int c_distinct = 0;
#if HIT_LOGGING
			int c_nohit = 0;
			int c_hits = 0;
			int minhit = int.MaxValue;
			int maxhit = int.MinValue;
#endif
			foreach (GlbCacheEntry[] rge in glb_cache)
				if (rge != null)
				{
					c_lists++;
					int l = rge.Length;
					c_total += l;
					if (l < min)
						min = l;
					if (l > max)
						max = l;
					foreach (var gce in rge)
					{
						int id0 = (int)(ushort)gce.k;
						int id1 = (int)(ushort)(gce.k >> 16);
						if (id0 == (int)(gce.f & Edge.Flag.MultiIdMask))
							throw new Exception();
						if (gce.f == Edge.Flag.Bottom)
							c_bot++;
						else if (id1 == (int)(gce.f & Edge.Flag.MultiIdMask))
							c_sub++;
						else
							c_distinct++;
					}
#if HIT_LOGGING
					foreach (var gce in rge)
					{
						int h = gce.c_hits;
						if (h == 0)
							c_nohit++;
						else
							c_hits += h;
						if (h < minhit)
							minhit = h;
						if (h > maxhit)
							maxhit = h;
					}
#endif
				}
			if (c_lists < c_buckets)
				min = 0;
			StringBuilder sb = new StringBuilder();
			sb.AppendLine("GLB cache status:");
			sb.AppendFormatLine("options: {0}", glb_cache_opts);
			sb.AppendFormatLine("buckets:          {0,8}", c_buckets);
			sb.AppendFormatLine("   bucket-load:   {0,8:0.000}", (double)c_total / c_buckets);
			if (c_lists > 0)
			{
				sb.AppendFormatLine("   in-use:        {0,8} ({1,6:0.00}%)", c_lists, c_lists * 100.0 / c_buckets);
				sb.AppendFormatLine("      min:        {0,8}", min);
				sb.AppendFormatLine("      max:        {0,8}", max);
				sb.AppendFormatLine("      load:       {0,8:0.000}", (double)c_total / c_lists);
			}
			sb.AppendFormatLine("entries:          {0,8}", c_total);
			sb.AppendFormatLine("   pre-cached:    {0,8}", c_precached);
			sb.AppendFormatLine("   demand-cached: {0,8}", c_total - c_precached);
			if (c_total > 0)
			{
				sb.AppendFormatLine("      subsume:    {0,8} ({1,6:0.00}%)", c_sub, c_sub * 100.0 / c_total);
				sb.AppendFormatLine("      distinct:   {0,8} ({1,6:0.00}%)", c_distinct, c_distinct * 100.0 / c_total);
				sb.AppendFormatLine("      bottom:     {0,8} ({1,6:0.00}%)", c_bot, c_bot * 100.0 / c_total);
			}

#if HIT_LOGGING
				s += String.Format("not-hit: {0} ({1:0.00}%) min-hit: {2} max-hit: {3} avg-hit: {4:0.00}",
					c_nohit,
					c_nohit * 100.0 / c_glb,
					minhit,
					maxhit,
					(double)c_hits / c_glb) + Environment.NewLine;

				foreach (var g in glb_cache.Where(rgrg => rgrg != null)
						.SelectMany()
						.GroupBy(gce => gce.c_hits)
						.OrderByDescending(grp => grp.Key))
				{
					s += String.Format("{0,6} ({1})" + Environment.NewLine, g.Key, g._Count());
					foreach (var gce in g.Take(4))
					{
						uint id0 = (uint)(ushort)gce.k;
						uint id1 = (uint)(ushort)(gce.k >> 16);
						s += String.Format("\t\t[{0}]{1}  [{2}]{3}  =>  {4}" + Environment.NewLine,
							type_arr[id0].Name,
							id0,
							type_arr[id1].Name,
							id1,
							gce.f < 0 ? "*bottom*" : "[" + ((TypeMgr)this).TypeNameOrStringValue(gce.f) + "]");
					}
				}
#endif
			return sb.ToString();
		}

		public void DisplayGlbCache()
		{
			foreach (GlbCacheEntry[] rggce in glb_cache)
			{
				if (rggce == null)
					continue;
				foreach (var gce in rggce)
				{
					uint id0 = (uint)(ushort)gce.k;
					uint id1 = (uint)(ushort)(gce.k >> 16);
					Console.WriteLine("[{0,25}]{1,4}  [{2,25}]{3,4}  =>  {4}",
						bcpo.type_arr[id0].Name,
						id0,
						bcpo.type_arr[id1].Name,
						id1,
						gce.f < 0 ? "*bottom*" : "[" + tu.TypeNameOrStringValue(gce.f) + "]");
				}
			}
		}
	};
}
